package com.company.ljh.medium;

import com.company.ljh.utils.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @description:
 * 437. 路径总和 III
 * 中等
 * 1.6K
 * 相关企业
 * 给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 *
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/4 17:46
 * @version:1.0
 */
public class 路径总和III {
    //2.前缀和法, 前缀和是指当前从root节点到当前节点路径的和
    //判断是否有和为target的值，只需要当前值的前缀和-前面路径中每个节点的前缀和是否为target，则表示当前节点到那个节点的路径和为target
    //
    public int pathSum(TreeNode root, int targetSum) {
        //保存最终结果，做全局累加
        int[] result = new int[]{0};
        //保存前缀和的值和出现次数
        HashMap<Long,Integer> prefixSumMap = new <Long,Integer>HashMap();
        //添加一条0，1，为了保证从root到当前节点的前缀和刚好为target的情况
        prefixSumMap.put(0l,1);
        prefixSum(root,prefixSumMap,0l,result,targetSum);
        return result[0];
    }

    public void prefixSum(TreeNode root,HashMap <Long,Integer> prefixSumMap,long sum,int [] result,int targetSum){
        if(root == null){
            return;
        }
        sum+=root.val;
        long findPrefixSum = sum - targetSum;
        if(prefixSumMap.containsKey(findPrefixSum)){
            //当前缀和为父节点时，findPrefixSum刚好等于当前节点的值，因此不需要考虑当前节点等于targetSum的情况
            result[0]+=prefixSumMap.get(findPrefixSum);
        }
        prefixSumMap.put(sum,prefixSumMap.getOrDefault(sum,0) + 1);
        //左节点递归
        prefixSum(root.left,prefixSumMap,sum,result,targetSum);
        prefixSum(root.right,prefixSumMap,sum,result,targetSum);
        int size = prefixSumMap.get(sum) -1;
        //去除当前节点的前缀和，防止影响到非当前路径的节点
        if(size > 0){
            prefixSumMap.put(sum,size);
        }else{
            prefixSumMap.remove(sum);
        }
    }

    //1.递归法，保存当前节点所有的路径和
    public int pathSum2(TreeNode root, int targetSum) {
        //保存最终结果，做全局累加
        int[] result = new int[]{0};
        traversalTree(root,result,targetSum);
        //返回包含当前节点的所有路径和
        return result[0];
    }

    public List<Long> traversalTree(TreeNode root,int []result,int targetSum){
        if(root==null){
            return null;
        }
        //使用int可能导致溢出
        List<Long> sumList = new ArrayList();
        if(root.val == targetSum){
            result[0]++;
        }
        sumList.add((long)root.val);
        List<Long> leftSumList = traversalTree(root.left,result,targetSum);
        if(leftSumList != null){
            for(long sum : leftSumList){
                if(sum+root.val == targetSum){
                    result[0]++;
                }
                sumList.add(sum+root.val);
            }
        }
        List<Long> rightSumList = traversalTree(root.right,result,targetSum);
        if(rightSumList != null){
            for(long sum : rightSumList){
                if(sum+root.val == targetSum){
                    result[0]++;
                }
                sumList.add(sum+root.val);
            }
        }
        return sumList;
    }
}
